/*
 * DisjointSet.cpp
 *
 *  Created on: 30 Oct 2013
 *      Author: Patrick
 */

#include <vector>
#include <algorithm>
#include <iostream>

#include "DisjointSet.hpp"

namespace Engine {

DisjointSet::DisjointSet() {}

DisjointSet::~DisjointSet() {
	for(unsigned int i = 0; i < this->nodes.size(); i++)
		delete this->nodes.at(i);

	this->nodes.clear();
}

void DisjointSet::insert(unsigned int x) {
	Node* n = new Node();
	n->value = x;
	n->parent = n;
	n->rank = 0;

	if(x >= this->nodes.size())
		nodes.resize(x + 1);

	nodes.at(x) = n;
}

int DisjointSet::findRootValue(int x) {
	Node* n = nodes.at(x);

	if(n->parent->value != n->value)
		n->parent = this->findRootNode(n->parent->value);

	return n->parent->value;
}

Node* DisjointSet::findRootNode(int x) {
	Node* n = this->nodes.at(x);

	if(n->parent->value != n->value)
		n->parent = this->findRootNode(n->parent->value);

	return n->parent;
}

//Node* DisjointSet::findRootNode(Node* n) {
//	if(n->parent->value != n->value)
//		n->parent = this->findRootNode(n->parent);
//
//	return n->parent;
//}

void DisjointSet::Union(int x, int y) {
	Node* rootX = this->findRootNode(x);
	Node* rootY = this->findRootNode(y);

	if(rootX->value == rootY->value)
		return;

	if(rootX->rank > rootY->rank) {
		rootY->parent = rootX;
		return;
	} else if(rootX->rank < rootY->rank) {
		rootX->parent = rootY;
		return;
	} else {
		rootY->parent = rootX;
		rootX->rank++;
	}
}

std::vector<int> DisjointSet::getRoots() {
	std::vector<int> result;
	for(unsigned int i = 0; i < this->nodes.size(); i++) {
		if(this->nodes.at(i) != 0) {
			Node* n = this->nodes.at(i);
			if(n->parent->value == n->value) {
				result.push_back(n->value);
			}
		}
	}

	return result;
}

}
